package com.kehao.leetcode.hard.tree_graph;

import com.kehao.utils.LeetCodeUtil;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

public class LongestIncreasingPathSolution {

    //记忆化搜索
    public int longestIncreasingPath(int[][] matrix) {
        int result = 0;
        int[][] increasePath = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                result = Math.max(result , dfs(matrix,increasePath,i,j));
            }
        }
        return result;
    }

    private int dfs(int[][] matrix, int[][] increasePath, int i, int j) {
        if(increasePath[i][j]!=0) return increasePath[i][j];
        int up=0, down=0 ,left=0 ,right =0;
        if(i>0&&matrix[i-1][j]<matrix[i][j]) up = dfs(matrix,increasePath,i-1,j);
        if(j>0&&matrix[i][j-1]<matrix[i][j]) left = dfs(matrix,increasePath,i,j-1);
        if(i+1< matrix.length && matrix[i+1][j]<matrix[i][j]) down = dfs(matrix,increasePath,i+1,j);
        if(j+1<matrix[0].length && matrix[i][j+1]<matrix[i][j]) right = dfs(matrix,increasePath,i,j+1);
        increasePath[i][j] = 1+Math.max(Math.max(up,left),Math.max(down,right));
        return increasePath[i][j];
    }


    //动态规划
    public int longestIncreasingPath1(int[][] matrix) {
        int[][] inDegree = new int[matrix.length][matrix[0].length];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(i>0&&matrix[i-1][j]<matrix[i][j]) inDegree[i][j]++;
                if(j>0&&matrix[i][j-1]<matrix[i][j]) inDegree[i][j]++;
                if(i+1< matrix.length && matrix[i+1][j]<matrix[i][j]) inDegree[i][j]++;
                if(j+1<matrix[0].length && matrix[i][j+1]<matrix[i][j]) inDegree[i][j]++;
                if(inDegree[i][j]==0) queue.add(new int[]{i,j});
            }
        }
        int result =0;
        while (!queue.isEmpty()){
            result++;
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] poll = queue.poll();
                int i = poll[0],j = poll[1];
                if(i>0&&matrix[i-1][j]>matrix[i][j]) {
                    inDegree[i-1][j]--;
                    if(inDegree[i-1][j]==0){
                        queue.add(new int[]{i-1,j});
                    }
                }
                if(j>0&&matrix[i][j-1]>matrix[i][j]) {
                    inDegree[i][j-1]--;
                    if(inDegree[i][j-1]==0){
                        queue.add(new int[]{i,j-1});
                    }
                }
                if(i+1< matrix.length && matrix[i+1][j]>matrix[i][j]) {
                    inDegree[i+1][j]--;
                    if(inDegree[i+1][j]==0){
                        queue.add(new int[]{i+1,j});
                    }
                }
                if(j+1<matrix[0].length && matrix[i][j+1]>matrix[i][j]) {
                    inDegree[i][j+1]--;
                    if(inDegree[i][j+1]==0){
                        queue.add(new int[]{i,j+1});
                    }
                }
            }

        }
        return result;
    }



    @Test
    public void test(){
        String s = "[[3,4,5],[3,2,6],[2,2,1]]";
        System.out.println(LeetCodeUtil.bracketTransform(s));
    }

    @Test
    public void test01(){
        int[][] matrix = {{9,9,4},{6,6,8},{2,1,1}};
        int result = longestIncreasingPath1(matrix);
        System.out.println(result);
    }

    @Test
    public void test02(){
        int[][] matrix = {{3,4,5},{3,2,6},{2,2,1}};
        int result = longestIncreasingPath1(matrix);
        System.out.println(result);
    }

    @Test
    public void test03(){
        int[][] matrix = {{1}};
        int result = longestIncreasingPath1(matrix);
        System.out.println(result);
    }


}
